package com.love.dynamicPlan;


/**
 *  概念：
 *  1）每个节点最多只能有两棵树，且有左右之分
 *  2）任意结点（包括根节点）的左子树上的结点的值都比这个结点的值小
 *  3）任意结点（包括根节点）的右子树上的结点的值都比这个结点的值大
 *  4）没有值相等的点
 *
 * 1） 中序遍历的数据严格递增
 *
 */
public class SearchTree {


    /***
     * 判断搜索二叉树
     */


    static class TreeNode{

        public int val;

        public TreeNode left;

        public TreeNode right;


        public TreeNode(int val,TreeNode left,TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public static class Info{

        public boolean isBST;

        public int max;

        public int min;

        public Info(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }


    // leftMaxVal < x < rightMinVal
    public static Info process(TreeNode x){
        // 如果空树就不反回任何信息，让调用者去判断
        if(x == null){
            return null;
        }
        // 为什么直接进来就递归呢，因为要调到最底层，才返回算其他信息
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int max = x.val;
        int min = x.val;

        if(leftInfo != null){
            max = Math.max(leftInfo.max,max);
            min = Math.min(leftInfo.min,min);
        }

        if(rightInfo != null){
            max = Math.max(rightInfo.max,max);
            min = Math.min(rightInfo.min,min);
        }

        boolean isBST = true;
        if(leftInfo != null && !leftInfo.isBST ){
            isBST = false;
        }
        if(rightInfo != null && !rightInfo.isBST){
            isBST = false;
        }


        // 这里的意思是 如果左树为空，左树是搜索二叉树，如果不为空，比较大小（下同理）
        boolean leftB = leftInfo == null ? true : (leftInfo.max < x.val);
        boolean rightB = rightInfo == null ? true : (rightInfo.min > x.val);

        if(leftB && rightB){
            isBST = true;
        }

        return new Info(isBST,max,min);


    }




}
